//
// Created by madison on 2022/7/12.
//

#include "string"

using namespace std;

/**
 * Definition for singly-linked list.
 **/
struct ListNode {
    int val;
    ListNode *next;

    ListNode() : val(0), next(nullptr) {}

    ListNode(int x) : val(x), next(nullptr) {}

    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution {
public:
    // 方法一：递归
    ListNode *mergeTwoLists(ListNode *list1, ListNode *list2) {
        if (list1 == nullptr) {
            return list2;
        } else if (list2 == nullptr) {
            return list1;
        } else if (list1->val < list2->val) {
            list1->next = mergeTwoLists(list1->next, list2);
            return list1;
        } else {
            list2->next = mergeTwoLists(list1, list2->next);
            return list2;
        }
    }

    // 方法二：迭代
    ListNode *mergeTwoLists1(ListNode *list1, ListNode *list2) {
        ListNode *preHead = new ListNode(-1);
        ListNode *prev = preHead;

        while (list1 != nullptr && list2 != nullptr) {
            if (list1->val < list2->val) {
                prev->next = list1;
                list1 = list1->next;
            } else {
                prev->next = list2;
                list2 = list2->next;
            }
            prev = prev->next;
        }

        // 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
        prev->next = list1 == nullptr ? list2 : list1;
        return preHead->next;
    }
};

int main() {
    ListNode *node2 = new ListNode(4);
    ListNode *node1 = new ListNode(2, node2);
    ListNode *list1 = new ListNode(1, node1);


    ListNode *node12 = new ListNode(4);
    ListNode *node11 = new ListNode(3, node12);
    ListNode *list2 = new ListNode(1, node11);


    Solution solution;
    ListNode *head = solution.mergeTwoLists1(list1, list2);
    ListNode *temp = head;
    while (temp) {
        printf("%d\t", temp->val);
        temp = temp->next;
    }
    return 0;
}